11736. Prime Time

For your math homework this week your teacher gave you five large numbers and asked you to find their prime factors. However these numbers aren't nearly large enough for someone with knowledge of programming like yourself. So you decide to take the factorial of each of these numbers. Recall that n! (n factorial) is the product of the integers from 1 through n (inclusive). It’s your job now to create a program to help you do your homework.

Input. Each test case contains a number n (2 ≤ n ≤ 10000).

Output. The output should contain a line representing the prime factorization of the factorial given number, which should be of the form: p₁^e₁ * p₂^e₂ * ... * p_k^e_k where p₁, p₂, ..., p_k are the distinct prime factors of the factorial of the given number in increasing order, and e₁, e₂, ..., e_k are their exponents.

Sample Input	Sample Output
10	2^8 * 3^4 * 5^2 * 7^1

РЕШЕНИЕ

разложение на множители

Анализ алгоритма

По заданному числу n следует найти разложение на простые множители числа n!

Реализация алгоритма

#include <cstdio>

#include <vector>

#include <cmath>

using namespace std;

vector<int> p, h;

int i, j, num, n, s;

void gen_primes(void)

{

int i, j;

vector<int> primes(10100);

for(i = 0; i < 10100; i++) primes[i] = 1;

primes[0] = primes[1] = 0;

for(i = 2; i <= (int)sqrt(10100.0); i++)

if (primes[i])

for(j = i * i; j < 10000; j += i) primes[j] = 0;

for(i = 2; i < 10100; i++)

if(primes[i]) p.push_back(i);

}

int main (void)

{

gen_primes();

scanf("%d",&num);

h.resize(10001);

for(j = 2; j <= num; j++)

{

n = j;

for(i = 0; p[i] <= n; i++)

{

while(n % p[i] == 0)

{

h[p[i]]++;

n = n / p[i];

}

}

}

s = 0;

for(i = 2; i <= num; i++)

if(h[i] != 0)

{

s++;

if(s > 1) printf(" * ");

printf("%d^%d",i,h[i]);

}

printf("\n");

return 0;

}